home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Tools / mkid / mkid.c < prev    next >
C/C++ Source or Header  |  1995-05-03  |  17KB  |  748 lines
  1. static char copyright[] = "@(#)Copyright (c) 1986, Greg McGary";
  2. static char sccsid[] = "@(#)mkid.c    1.4 86/11/06";
  3.  
  4. #include    <bool.h>
  5. #include    <sys/types.h>
  6. #include    <sys/stat.h>
  7. #include    <stdio.h>
  8. #include    <string.h>
  9. #include    <ctype.h>
  10. #include    <id.h>
  11. #include    <bitops.h>
  12. #include    <errno.h>
  13. #include    <extern.h>
  14.  
  15. int idnHashCmp();
  16. int idnQsortCmp();
  17. int round2();
  18. struct idname *newIdName();
  19. void extractId();
  20. void fileIdArgs();
  21. void initHashTable();
  22. void oldIdArgs();
  23. void rehash();
  24. void updateID();
  25. void writeID();
  26.  
  27. long    NameCount;        /* Count of names in database */
  28. long    NumberCount;        /* Count of numbers in database */
  29. long    StringCount;        /* Count of strings in database */
  30. long    SoloCount;        /* Count of identifiers that occur only once */
  31.  
  32. long    HashSize;        /* Total Slots in hash table */
  33. long    HashMaxLoad;        /* Maximum loading of hash table */
  34. long    HashFill;        /* Number of keys inserted in table */
  35. long    HashProbes;        /* Total number of probes */
  36. long    HashSearches;        /* Total number of searches */
  37. struct idname    **HashTable;    /* Vector of idname pointers */
  38.  
  39. bool    Verbose = FALSE;
  40.  
  41. int    ArgsCount = 0;        /* Count of args to save */
  42. int    ScanCount = 0;        /* Count of files to scan */
  43. int    PathCount = 0;        /* Count of files covered in database */
  44. int    BitArraySize;        /* Size of bit array slice (per name) */
  45.  
  46.  
  47. char    *MyName;
  48. static void
  49. usage()
  50. {
  51.     fprintf(stderr, "Usage: %s [-f<idfile>] [-s<dir>] [-r<dir>] [(+|-)l[<lang>]] [-v] [(+|-)S<scanarg>] [-a<argfile>] [-] [-u] [files...]\n", MyName);
  52.     exit(1);
  53. }
  54. main(argc, argv)
  55.     int        argc;
  56.     char        **argv;
  57. {
  58.     char        *arg;
  59.     int        op;
  60.     FILE        *argFILE = NULL;
  61.     char        *idFile = IDFILE;
  62.     char        *rcsDir = NULL;
  63.     char        *sccsDir = NULL;
  64.     struct idarg    *idArgs, *idArgHead;
  65.     bool        keepLang = FALSE;
  66.     int        argsFrom = 0;
  67. #define    AF_CMDLINE    0x1    /* file args came on command line */
  68. #define    AF_FILE        0x2    /* file args came from a file (-f<file>) */
  69. #define    AF_IDFILE    0x4    /* file args came from an old ID file (-u) */
  70. #define    AF_QUERY    0x8    /* no file args necessary: usage query */
  71.  
  72.     MyName = basename(GETARG(argc, argv));
  73. #ifdef ERRLINEBUF
  74.     setlinebuf(stderr);
  75. #endif
  76.  
  77.     idArgs = idArgHead = NEW(struct idarg);
  78.  
  79.     /*
  80.         Process some arguments, and snarf-up some
  81.         others for processing later.
  82.     */
  83.     while (argc) {
  84.         arg = GETARG(argc, argv);
  85.         if (*arg != '-' && *arg != '+') {
  86.             argsFrom |= AF_CMDLINE;
  87.             idArgs->ida_arg = arg;
  88.             idArgs->ida_flags = IDA_SCAN|IDA_PATH;
  89.             idArgs->ida_index = postIncr(&PathCount);
  90.             ScanCount++;
  91.             idArgs = (idArgs->ida_next = NEW(struct idarg));
  92.             continue;
  93.         }
  94.         op = *arg++;
  95.         switch (*arg++)
  96.         {
  97.         case 'u':
  98.             argsFrom |= AF_IDFILE;
  99.             oldIdArgs(idFile, &idArgs);
  100.             break;
  101.         case '\0':
  102.             argsFrom |= AF_FILE;
  103.             fileIdArgs(stdin, &idArgs);
  104.             break;
  105.         case 'a':
  106.             if ((argFILE = fopen(arg, "r")) == NULL) {
  107.                 filerr("open", arg);
  108.                 exit(1);
  109.             }
  110.             argsFrom |= AF_FILE;
  111.             fileIdArgs(argFILE, &idArgs);
  112.             break;
  113.         case 'f':
  114.             idFile = arg;
  115.             break;
  116.         case 'v':
  117.             Verbose = TRUE;
  118.             break;
  119.         case 'S':
  120.             if (strchr(&arg[-2], '?')) {
  121.                 setScanArgs(op, arg);
  122.                 argsFrom |= AF_QUERY;
  123.             }
  124.             /*FALLTHROUGH*/
  125.         case 'l':
  126.         case 's':
  127.         case 'r':
  128.             idArgs->ida_arg = &arg[-2];
  129.             idArgs->ida_index = -1;
  130.             idArgs->ida_flags = IDA_ARG;
  131.             idArgs = (idArgs->ida_next = NEW(struct idarg));
  132.             ArgsCount++;
  133.             break;
  134.         default:
  135.             usage();
  136.         }
  137.     }
  138.  
  139.     if (argsFrom & AF_QUERY)
  140.         exit(0);
  141.     /*
  142.         File args should only come from one place.  Ding the
  143.         user if arguments came from multiple places, or if none
  144.         were supplied at all.
  145.     */
  146.     switch (argsFrom)
  147.     {
  148.     case AF_CMDLINE:
  149.     case AF_FILE:
  150.     case AF_IDFILE:
  151.         if (PathCount > 0)
  152.             break;
  153.         /*FALLTHROUGH*/
  154.     case 0:
  155.         fprintf(stderr, "%s: Use -u, -f<file>, or cmd-line for file args!\n", MyName);
  156.         usage();
  157.     default:
  158.         fprintf(stderr, "%s: Use only one of: -u, -f<file>, or cmd-line for file args!\n", MyName);
  159.         usage();
  160.     }
  161.  
  162.     if (ScanCount == 0)
  163.         exit(0);
  164.  
  165.     BitArraySize = (PathCount + 7) >> 3;
  166.     initHashTable(ScanCount);
  167.  
  168.     if (access(idFile, 06) < 0
  169.     && (errno != ENOENT || access(dirname(idFile), 06) < 0)) {
  170.         filerr("modify", idFile);
  171.         exit(1);
  172.     }
  173.  
  174.     for (idArgs = idArgHead; idArgs->ida_next; idArgs = idArgs->ida_next) {
  175.         char        *(*scanner)();
  176.         FILE        *srcFILE;
  177.         char        *arg, *lang, *suff;
  178.  
  179.         lang = NULL;
  180.         arg = idArgs->ida_arg;
  181.         if (idArgs->ida_flags & IDA_ARG) {
  182.             op = *arg++;
  183.             switch (*arg++)
  184.             {
  185.             case 'l':
  186.                 if (*arg == '\0') {
  187.                     keepLang = FALSE;
  188.                     lang = NULL;
  189.                     break;
  190.                 }
  191.                 if (op == '+')
  192.                     keepLang = TRUE;
  193.                 lang = arg;
  194.                 break;
  195.             case 's':
  196.                 sccsDir = arg;
  197.                 break;
  198.             case 'r':
  199.                 rcsDir = arg;
  200.                 break;
  201.             case 'S':
  202.                 setScanArgs(op, strsav(arg));
  203.                 break;
  204.             default:
  205.                 usage();
  206.             }
  207.             continue;
  208.         }
  209.         if (!(idArgs->ida_flags & IDA_SCAN))
  210.             goto skip;
  211.         if (lang == NULL) {
  212.             if ((suff = strrchr(arg, '.')) == NULL)
  213.                 suff = "";
  214.             if ((lang = getLanguage(suff)) == NULL) {
  215.                 fprintf(stderr, "%s: No language assigned to suffix: `%s'\n", MyName, suff);
  216.                 goto skip;
  217.             }
  218.         }
  219.         if ((scanner = getScanner(lang)) == NULL) {
  220.             fprintf(stderr, "%s: No scanner for language: `%s'\n", MyName, lang);
  221.             goto skip;
  222.         }
  223.         if ((srcFILE = openSrcFILE(arg, sccsDir, rcsDir)) == NULL)
  224.             goto skip;
  225.         if (Verbose)
  226.             fprintf(stderr, "%s: %s\n", lang, arg);
  227.         extractId(scanner, srcFILE, idArgs->ida_index);
  228.         fclose(srcFILE);
  229.     skip:
  230.         if (!keepLang)
  231.             lang = NULL;
  232.     }
  233.  
  234.     if (HashFill == 0)
  235.         exit(0);
  236.  
  237.     if (Verbose)
  238.         fprintf(stderr, "Compressing Hash Table...\n");
  239.     hashCompress(HashTable, HashSize);
  240.     if (Verbose)
  241.         fprintf(stderr, "Sorting Hash Table...\n");
  242.     qsort(HashTable, HashFill, sizeof(struct idname *), idnQsortCmp);
  243.  
  244.     if (argsFrom == AF_IDFILE) {
  245.         if (Verbose)
  246.             fprintf(stderr, "Merging Tables...\n");
  247.         updateID(idFile, idArgHead);
  248.     }
  249.  
  250.     if (Verbose)
  251.         fprintf(stderr, "Writing `%s'...\n", idFile);
  252.     writeID(idFile, idArgHead);
  253.  
  254.     if (Verbose) {
  255.         float loadFactor = (float)HashFill / (float)HashSize;
  256.         float aveProbes = (float)HashProbes / (float)HashSearches;
  257.         float aveOccur = (float)HashSearches / (float)HashFill;
  258.         fprintf(stderr, "Names: %ld, ", NameCount);
  259.         fprintf(stderr, "Numbers: %ld, ", NumberCount);
  260.         fprintf(stderr, "Strings: %ld, ", StringCount);
  261.         fprintf(stderr, "Solo: %ld, ", SoloCount);
  262.         fprintf(stderr, "Total: %ld\n", HashFill);
  263.         fprintf(stderr, "Occurances: %.2f, ", aveOccur);
  264.         fprintf(stderr, "Load: %.2f, ", loadFactor);
  265.         fprintf(stderr, "Probes: %.2f\n", aveProbes);
  266.     }
  267.     exit(0);
  268. }
  269.  
  270. void
  271. extractId(getId, srcFILE, index)
  272.     register char    *(*getId)();
  273.     register FILE    *srcFILE;
  274.     int        index;
  275. {
  276.     register struct idname    **slot;
  277.     register char    *key;
  278.     int        flags;
  279.  
  280.     while ((key = (*getId)(srcFILE, &flags)) != NULL) {
  281.         slot = (struct idname **)hashSearch(key, HashTable, HashSize, sizeof(struct idname *), h1str, h2str, idnHashCmp, &HashProbes);
  282.         HashSearches++;
  283.         if (*slot != NULL) {
  284.             (*slot)->idn_flags |= flags;
  285.             BITSET((*slot)->idn_bitv, index);
  286.             continue;
  287.         }
  288.         *slot = newIdName(key);
  289.         (*slot)->idn_flags = IDN_SOLO|flags;
  290.         BITSET((*slot)->idn_bitv, index);
  291.         if (HashFill++ >= HashMaxLoad)
  292.             rehash();
  293.     }
  294. }
  295.  
  296. void
  297. writeID(idFile, idArgs)
  298.     char        *idFile;
  299.     struct idarg    *idArgs;
  300. {
  301.     register struct idname    **idnp;
  302.     register struct idname    *idn;
  303.     register int    i;
  304.     char        *vecBuf;
  305.     FILE        *idFILE;
  306.     int        count;
  307.     int        lasti;
  308.     long        before, after;
  309.     int        length, longest;
  310.     struct idhead    idh;
  311.  
  312.     if ((idFILE = fopen(idFile, "w+")) == NULL) {
  313.         filerr("create", idFile);
  314.         exit(1);
  315.     }
  316.     fseek(idFILE, (long)sizeof(struct idhead), 0);
  317.  
  318.     /* write out the list of pathnames */
  319.     idh.idh_argo = ftell(idFILE);
  320.     for (i = lasti = 0; idArgs->ida_next; idArgs = idArgs->ida_next) {
  321.         if (idArgs->ida_index > 0)
  322.             while (++lasti < idArgs->ida_index)
  323.                 i++, putc('\0', idFILE);
  324.         fputs(idArgs->ida_arg, idFILE);
  325.         i++, putc('\0', idFILE);
  326.     }
  327.     idh.idh_argc = i;
  328.     idh.idh_pthc = PathCount;
  329.  
  330.     /* write out the list of identifiers */
  331.     i = 1;
  332.     if (idh.idh_pthc >= 0x000000ff)
  333.         i++;
  334.     if (idh.idh_pthc >= 0x0000ffff)
  335.         i++;
  336.     if (idh.idh_pthc >= 0x00ffffff)
  337.         i++;
  338.     idh.idh_vecc = i;
  339.  
  340.     vecBuf = malloc((idh.idh_pthc + 1) * idh.idh_vecc);
  341.  
  342.     putc('\377', idFILE);
  343.     before = idh.idh_namo = ftell(idFILE);
  344.     longest = 0;
  345.     for (idnp = HashTable, i = 0; i < HashFill; i++, idnp++) {
  346.         idn = *idnp;
  347.         if (idn->idn_name[0] == '\0') {
  348.             HashFill--; i--;
  349.             continue;
  350.         }
  351.         if (idn->idn_flags & IDN_SOLO)
  352.             SoloCount++;
  353.         if (idn->idn_flags & IDN_NUMBER)
  354.             NumberCount++;
  355.         if (idn->idn_flags & IDN_NAME)
  356.             NameCount++;
  357.         if (idn->idn_flags & IDN_STRING)
  358.             StringCount++;
  359.  
  360.         putc((*idnp)->idn_flags, idFILE);
  361.         fputs(idn->idn_name, idFILE);
  362.         putc('\0', idFILE);
  363.  
  364.         count = bitsToVec(vecBuf, (*idnp)->idn_bitv, idh.idh_pthc, idh.idh_vecc);
  365.         fwrite(vecBuf, idh.idh_vecc, count, idFILE);
  366.         putc('\377', idFILE);
  367.         after = ftell(idFILE);
  368.         
  369.         if ((length = (after - before)) > longest)
  370.             longest = length;
  371.         before = after;
  372.     }
  373.     idh.idh_namc = i;
  374.     putc('\377', idFILE);
  375.     idh.idh_endo = ftell(idFILE);
  376.     idh.idh_bsiz = longest;
  377.  
  378.     /* write out the header */
  379.     strncpy(idh.idh_magic, IDH_MAGIC, sizeof(idh.idh_magic));
  380.     idh.idh_vers = IDH_VERS;
  381.     fseek(idFILE, 0L, 0);
  382.     fwrite(&idh, sizeof(struct idhead), 1, idFILE);
  383.  
  384.     fclose(idFILE);
  385. }
  386.  
  387. /*
  388.     Build an idarg vector from pathnames contained in an existing
  389.     id file.  Only include pathnames for files whose modification
  390.     time is later than that of the id file itself.
  391. */
  392. void
  393. oldIdArgs(idFile, idArgsP)
  394.     char        *idFile;
  395.     struct idarg    **idArgsP;
  396. {
  397.     struct stat    statBuf;
  398.     struct idhead    idh;
  399.     FILE        *idFILE;
  400.     register int    i;
  401.     register char    *strings;
  402.     time_t        idModTime;
  403.  
  404.     if ((idFILE = fopen(idFile, "r")) == NULL) {
  405.         filerr("open", idFile);
  406.         usage();
  407.     }
  408.     /*
  409.     *  Open the id file, get its mod-time, and read its header.
  410.     */
  411.     if (fstat(fileno(idFILE), &statBuf) < 0) {
  412.         filerr("stat", idFile);
  413.         usage();
  414.     }
  415.     idModTime = statBuf.st_mtime;
  416.     fread(&idh, sizeof(struct idhead), 1, idFILE);
  417.     if (!strnequ(idh.idh_magic, IDH_MAGIC, sizeof(idh.idh_magic))) {
  418.         fprintf(stderr, "%s: Not an id file: `%s'\n", MyName, idFile);
  419.         exit(1);
  420.     }
  421.     if (idh.idh_vers != IDH_VERS) {
  422.         fprintf(stderr, "%s: ID version mismatch (%ld,%ld)\n", MyName, idh.idh_vers, IDH_VERS);
  423.         exit(1);
  424.     }
  425.  
  426.     /*
  427.     *  Read in the id pathnames, compare their mod-times with
  428.     *  the id file, and incorporate the pathnames of recently modified 
  429.     *  files in the idarg vector.  Also, construct a mask of
  430.     *  bit array positions we want to turn off when we build the
  431.     *  initial hash-table.
  432.     */
  433.     fseek(idFILE, idh.idh_argo, 0);
  434.     strings = malloc(i = idh.idh_namo - idh.idh_argo);
  435.     fread(strings, i, 1, idFILE);
  436.     ScanCount = 0;
  437.     for (i = 0; i < idh.idh_argc; i++) {
  438.         (*idArgsP)->ida_arg = strings;
  439.         if (*strings == '+' || *strings == '-') {
  440.             (*idArgsP)->ida_flags = IDA_ARG;
  441.             (*idArgsP)->ida_index = -1;
  442.         } else {
  443.             (*idArgsP)->ida_flags = IDA_PATH;
  444.             (*idArgsP)->ida_index = postIncr(&PathCount);
  445.             if (stat(strings, &statBuf) < 0) {
  446.                 filerr("stat", strings);
  447.             } else if (statBuf.st_mtime >= idModTime) {
  448.                 (*idArgsP)->ida_flags |= IDA_SCAN;
  449.                 ScanCount++;
  450.             }
  451.         }
  452.         (*idArgsP) = ((*idArgsP)->ida_next = NEW(struct idarg));
  453.         while (*strings++)
  454.             ;
  455.     }
  456.     if (ScanCount == 0) {
  457.         fclose(idFILE);
  458.         exit(0);
  459.     }
  460.     fclose(idFILE);
  461. }
  462.  
  463. void
  464. updateID(idFile, idArgs)
  465.     char        *idFile;
  466.     struct idarg    *idArgs;
  467. {
  468.     struct idname    *idn;
  469.     struct idhead    idh;
  470.     register char    *bitArray;
  471.     char        *entry;
  472.     register int    i;
  473.     FILE        *idFILE;
  474.     int        cmp, count, size;
  475.     char        *bitsOff;
  476.     struct idname    **newTable, **mergeTable;
  477.     struct idname    **t1, **t2, **tm;
  478.  
  479.     if ((idFILE = fopen(idFile, "r")) == NULL)
  480.         filerr("open", idFile);
  481.     fread(&idh, sizeof(struct idhead), 1, idFILE);
  482.  
  483.     entry = malloc(idh.idh_bsiz);
  484.  
  485.     bitsOff = malloc(BitArraySize);
  486.     bzero(bitsOff, BitArraySize);
  487.     for (i = 0; idArgs->ida_next; idArgs = idArgs->ida_next)
  488.         if (idArgs->ida_flags & IDA_SCAN)
  489.             BITSET(bitsOff, idArgs->ida_index);
  490.  
  491.     bitArray = malloc(BitArraySize);
  492.     bzero(bitArray, BitArraySize);
  493.     t2 = newTable = (struct idname **)malloc((idh.idh_namc + 1) * sizeof(struct idname *));
  494.     fseek(idFILE, idh.idh_namo, 0);
  495.     count = 0;
  496.     for (i = 0; i < idh.idh_namc; i++) {
  497.         size = 1 + fgets0(entry, idh.idh_bsiz, idFILE);
  498.         getsFF(&entry[size], idFILE);
  499.         vecToBits(bitArray, &entry[size], idh.idh_vecc);
  500.         bitsclr(bitArray, bitsOff, BitArraySize);
  501.         if (!bitsany(bitArray, BitArraySize))
  502.             continue;
  503.         *t2 = newIdName(ID_STRING(entry));
  504.         bitsset((*t2)->idn_bitv, bitArray, BitArraySize);
  505.         (*t2)->idn_flags = ID_FLAGS(entry);
  506.         bzero(bitArray, BitArraySize);
  507.         t2++; count++;
  508.     }
  509.     *t2 = NULL;
  510.  
  511.     t1 = HashTable;
  512.     t2 = newTable;
  513.     tm = mergeTable = (struct idname **)calloc(HashFill + count + 1, sizeof(struct idname *));
  514.     while (*t1 && *t2) {
  515.         cmp = strcmp((*t1)->idn_name, (*t2)->idn_name);
  516.         if (cmp < 0)
  517.             *tm++ = *t1++;
  518.         else if (cmp > 0)
  519.             *tm++ = *t2++;
  520.         else {
  521.             (*t1)->idn_flags |= (*t2)->idn_flags;
  522.             (*t1)->idn_flags &= ~IDN_SOLO;
  523.             bitsset((*t1)->idn_bitv, (*t2)->idn_bitv, BitArraySize);
  524.             *tm++ = *t1;
  525.             t1++, t2++;
  526.         }
  527.     }
  528.     while (*t1)
  529.         *tm++ = *t1++;
  530.     while (*t2)
  531.         *tm++ = *t2++;
  532.     *tm = NULL;
  533.     HashTable = mergeTable;
  534.     HashFill = tm - mergeTable;
  535. }
  536.  
  537. /*
  538.     Cons up a list of idArgs as supplied in a file.
  539. */
  540. void
  541. fileIdArgs(argFILE, idArgsP)
  542.     FILE        *argFILE;
  543.     struct idarg    **idArgsP;
  544. {
  545.     int        fileCount;
  546.     char        buf[BUFSIZ];
  547.     char        *arg;
  548.  
  549.     fileCount = 0;
  550.     while (fgets(buf, sizeof(buf), argFILE)) {
  551.         (*idArgsP)->ida_arg = arg = strnsav(buf, strlen(buf)-1);
  552.         if (*arg == '+' || *arg == '-') {
  553.             (*idArgsP)->ida_flags = IDA_ARG;
  554.             (*idArgsP)->ida_index = -1;
  555.         } else {
  556.             (*idArgsP)->ida_flags = IDA_SCAN|IDA_PATH;
  557.             (*idArgsP)->ida_index = postIncr(&PathCount);
  558.             ScanCount++;
  559.         }
  560.         (*idArgsP) = ((*idArgsP)->ida_next = NEW(struct idarg));
  561.     }
  562. }
  563.  
  564. void
  565. initHashTable(pathCount)
  566.     int        pathCount;
  567. {
  568.     if ((HashSize = round2((pathCount << 6) + 511)) > 0x8000)
  569.         HashSize = 0x8000;
  570.     HashMaxLoad = HashSize - (HashSize >> 4);    /* about 94% */
  571.     HashTable = (struct idname **)calloc(HashSize, sizeof(struct idname *));
  572. }
  573.  
  574. /*
  575.     Double the size of the hash table in the
  576.     event of overflow...
  577. */
  578. void
  579. rehash()
  580. {
  581.     long        oldHashSize = HashSize;
  582.     struct idname    **oldHashTable = HashTable;
  583.     register struct idname    **htp;
  584.     register struct idname    **slot;
  585.  
  586.     HashSize *= 2;
  587.     if (Verbose)
  588.         fprintf(stderr, "Rehashing... (doubling size to %ld)\n", HashSize);
  589.     HashMaxLoad = HashSize - (HashSize >> 4);
  590.     HashTable = (struct idname **)calloc(HashSize, sizeof(struct idname *));
  591.  
  592.     HashFill = 0;
  593.     for (htp = oldHashTable; htp < &oldHashTable[oldHashSize]; htp++) {
  594.         if (*htp == NULL)
  595.             continue;
  596.         slot = (struct idname **)hashSearch((*htp)->idn_name, (char *)HashTable, HashSize, sizeof(struct idname *), h1str, h2str, idnHashCmp, &HashProbes);
  597.         if (*slot) {
  598.             fprintf(stderr, "%s: Duplicate hash entry!\n");
  599.             exit(1);
  600.         }
  601.         *slot = *htp;
  602.         HashSearches++;
  603.         HashFill++;
  604.     }
  605.     free(oldHashTable);
  606. }
  607.  
  608. /*
  609.     Round a given number up to the nearest power of 2.
  610. */
  611. int
  612. round2(rough)
  613.     int        rough;
  614. {
  615.     int        round;
  616.  
  617.     round = 1;
  618.     while (rough) {
  619.         round <<= 1;
  620.         rough >>= 1;
  621.     }
  622.     return round;
  623. }
  624.  
  625. /*
  626.     `compar' function for hashSearch()
  627. */
  628. int
  629. idnHashCmp(key, idn)
  630.     char        *key;
  631.     struct idname    **idn;
  632. {
  633.     int        collate;
  634.  
  635.     if (*idn == NULL)
  636.         return 0;
  637.     
  638.     if ((collate = strcmp(key, (*idn)->idn_name)) == 0)
  639.         (*idn)->idn_flags &= ~IDN_SOLO;    /* we found another occurance */
  640.  
  641.     return collate;
  642. }
  643.  
  644. /*
  645.     `compar' function for qsort().
  646. */
  647. int
  648. idnQsortCmp(idn1, idn2)
  649.     struct idname    **idn1;
  650.     struct idname    **idn2;
  651. {
  652.     if (*idn1 == *idn2)
  653.         return 0;
  654.     if (*idn1 == NULL)
  655.         return 1;
  656.     if (*idn2 == NULL)
  657.         return -1;
  658.  
  659.     return strcmp((*idn1)->idn_name, (*idn2)->idn_name);
  660. }
  661.  
  662. /*
  663.     Allocate a new idname struct and fill in the name field.
  664.     We allocate memory in large chunks to avoid frequent
  665.     calls to malloc() which is a major pig.
  666. */
  667. struct idname *
  668. newIdName(name)
  669.     char        *name;
  670. {
  671.     register struct idname    *idn;
  672.     register char    *allocp;
  673.     register int    allocsiz;
  674.     static char    *allocBuf = NULL;
  675.     static char    *allocEnd = NULL;
  676. #define    ALLOCSIZ    (8*1024)
  677.  
  678.     allocsiz = sizeof(struct idname) + strlen(name) + 1 + BitArraySize;
  679.     allocsiz += (sizeof(long) - 1);
  680.     allocsiz &= ~(sizeof(long) - 1);
  681.  
  682.     allocp = allocBuf;
  683.     allocBuf += allocsiz;
  684.     if (allocBuf > allocEnd) {
  685.         allocBuf = malloc(ALLOCSIZ);
  686.         allocEnd = &allocBuf[ALLOCSIZ];
  687.         allocp = allocBuf;
  688.         allocBuf += allocsiz;
  689.     }
  690.  
  691.     idn = (struct idname *)allocp;
  692.     allocp += sizeof(struct idname);
  693.     idn->idn_bitv = allocp;
  694.     for (allocsiz = BitArraySize; allocsiz--; allocp++)
  695.         *allocp = '\0';
  696.     idn->idn_name = strcpy(allocp, name);
  697.  
  698.     return idn;
  699. }
  700.  
  701. int
  702. postIncr(ip)
  703.     int        *ip;
  704. {
  705.     register int    i;
  706.     int        save;
  707.  
  708.     save = *ip;
  709.     i = save + 1;
  710.     if ((i & 0x00ff) == 0x00ff)
  711.         i++;
  712.     if ((i & 0xff00) == 0xff00)    /* This isn't bloody likely */
  713.         i += 0x100;
  714.     *ip = i;
  715.  
  716.     return save;
  717. }
  718.  
  719. /*
  720.     Move all non-NULL table entries to the front of the table.
  721.     return the number of non-NULL elements in the table.
  722. */
  723. int
  724. hashCompress(table, size)
  725.     char        **table;
  726.     int        size;
  727. {
  728.     register char    **front;
  729.     register char    **back;
  730.  
  731.     front = &table[-1];
  732.     back = &table[size];
  733.  
  734.     for (;;) {
  735.         while (*--back == NULL)
  736.             ;
  737.         if (back < front)
  738.             break;
  739.         while (*++front != NULL)
  740.             ;
  741.         if (back < front)
  742.             break;
  743.         *front = *back;
  744.     }
  745.  
  746.     return (back - table + 1);
  747. }
  748.